package Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:利用双链表模拟实现队列各种方法
 * User: 阿宾
 * Date: 2024-11-14
 * Time: 13:31
 */
public class MyQueue {
    //创建双链表节点
     private static class ListNode{
         int val;
         ListNode prev;
         ListNode next;

         public ListNode(int val){
             this.val = val;
         }
    }
    int size = 0;//表示当前队列元素元素个数
    ListNode first;//指向队列第一个节点
    ListNode last;//指向队列最后一个节点
    /**
     * 利用双链表尾插法插入队列元素
     * @param e
     */
    public void offer(int e){
        //1.创建新节点
        ListNode newNode = new ListNode(e);
        //2.判断队列是否为空
        if(first == null){
            first = newNode;
            //last = newNode;
        }else {
            last.next = newNode;
            newNode.prev = last;
            //last = newNode;
        }
        last = newNode;
        size++;
    }

    /**
     * 利用双链表头删法删除队头元素
     * @return 返回删除元素
     */
    public int poll(){
        int ret = 0;//用于返回值
        //1.判断队列是否为空
        if(first == null){
            System.out.println("队列为空，删除失败");
            return -1;//表示删除失败
        }
        //2.判断队列中是否只有一个元素
        if(first == last){
            ret = first.val;
            first = last = null;
        }else {
            //3.其他情况
            ret = first.val;
            first = first.next;
            first.prev.next = null;//断旧first到新first的链
            first.prev = null;//断新first到旧first的链
        }
        size--;
        return ret;
    }

    /**
     * 获取队头元素
     * @return 队头元素
     */
    public int peek(){
        if(first == null){
            //队列为空
            return -1;
        }
        return first.val;
    }

    /**
     * 获取队列有效元素个数
     * @return 元素个数
     */
    public int size(){
        return size;
    }

    /**
     * 检查队列是否为空
     * @return 空返回true，不空返回false
     */
    public boolean isEmpty(){

        return first == null;
    }

}
